/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        701.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/15 22:24
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。
// 返回插入后二叉搜索树的根节点。
// 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
//
//注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
#include "../header.h"

class Solution {
public:
    TreeNode *insertIntoBST(TreeNode *root, int val) {
        if (root == nullptr)
            return new TreeNode(val);
        if (root->val > val)
            root->left = insertIntoBST(root->left, val);
        else
            root->right = insertIntoBST(root->right, val);
        return root;
    }
};

